package com.wwz.leetcode;

import com.wwz.common.ListNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 执行用时：7 ms, 在所有Java提交中击败了26.91%的用户
 * 内存消耗：43 MB, 在所有Java提交中击败了87.24%的用户
 */
public class LeetCode23 {

    public ListNode mergeKLists(ListNode[] lists) {
        // 特判
        if (lists.length == 0) {
            return null;
        }
        ListNode listNode = new ListNode();
        List<Integer> res = new ArrayList<>();
        // 把listNode 放到了 Arraylist里面去
        for (int i = 0; i < lists.length; i++) {
            while (lists[i] != null) {
                res.add(lists[i].val);
                lists[i] = lists[i].next;
            }
        }
        // 特判
        if(res.size() == 0) {
            return null;
        }

        // 快排
        sort(res, 0, res.size() - 1);
        ListNode cur = listNode;
        // 拼回去
        for (int i = 0; i < res.size(); i++) {
            cur.val = res.get(i);
            // 摘掉最后一个节点
            if (i == res.size() - 1) {
                break;
            }
            cur.next = new ListNode();
            cur = cur.next;

        }
        return listNode;
    }

    // 排序方法
    public void sort(List<Integer> list, int left, int right) {
        if (left < right) {
            int index = quick(list, left, right);
            sort(list, left, index - 1);
            sort(list, index + 1, right);
        }
    }

    // 快排实现
    private int quick(List<Integer> list, int left, int right) {
        int pivot = list.get(left);
        while (left < right) {
            while (left < right && list.get(right) >= pivot) {
                right--;
            }
            list.set(left, list.get(right));
            while (left < right && list.get(left) <= pivot) {
                left++;
            }
            list.set(right, list.get(left));
        }
        list.set(left, pivot);
        return left;
    }

    @Test
    public void test() {
        ListNode listNode3 = new ListNode(5, null);
        ListNode listNode2 = new ListNode(4, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        ListNode listNode23 = new ListNode(4, null);
        ListNode listNode22 = new ListNode(3, listNode23);
        ListNode listNode21 = new ListNode(1, listNode22);
        ListNode[] lists = {listNode1, listNode21};
        ListNode res = mergeKLists(lists);
        System.out.println(res);
    }
}
